In this paper, we construct and investigate a hierarchy of spatio-temporalformalisms that result from various combinations of propositional spatial andtemporal logics such as the propositional temporal logic PTL, the spatiallogics RCC-8, BRCC-8, S4u and their fragments. The obtained results give aclear picture of the trade-off between expressiveness and computationalrealisability within the hierarchy. We demonstrate how different combiningprinciples as well as spatial and temporal primitives can produce NP-, PSPACE-,EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics outof components that are at most NP- or PSPACE-complete.
展开▼
